#include<iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
    int isfill[10], z[10], y[10];
    stack<int>xt;
    stack<int> tt;
    int count = 0;
    vector<vector<string>> ans;
    vector<vector<string>> solveNQueens(int n) {

        for (int i = 0; i < n; i++)
        {
            sol(0, i, n);
        }
        return ans;
    }
    int toz(int* a, int c, int n)
    {
        int ans = a[0] & 1;
        for (int i = 0; i <= n / 32; i++)
        {
            a[i] >>= 1;
            a[i] |= (a[i + 1] & 1) << 31;
        }
        if (c)
        {
            a[n / 32] |= 1 << (n % 32);
        }
        return ans;
    }
    int toy(int* a, int c, int n)
    {
        int t, ans;
        t = n % 32;
        ans = a[n / 32] & (1 << t);
        a[n / 32] -= ans;
        for (int i = 0; i <= n / 32; i++)
        {
            t = a[i] & (1 << 31);
            a[i] <<= 1;
            if (c)a[i] |= 1;
            c = t;
        }
        return ans;
    }
    bool sol(int i, int j, int n)
    {
        if (i >= n)
        {
            string str = "";
            vector<string> vect;
            while (!xt.empty())
            {
                for (int c = 0; c < n; c++)
                {
                    if (c == xt.top())str.push_back('Q');
                    else str.push_back('.');
                }
                vect.push_back(str);
                str.clear();
                tt.push(xt.top());
                xt.pop();
            }
            ans.push_back(vect);
            count++;
            while (!tt.empty())
            {
                xt.push(tt.top());
                tt.pop();
            }
            return 1;
        }
        if (i == 0)
        {
            memset(isfill, 0, sizeof isfill);
            memset(z, 0, sizeof z);
            memset(y, 0, sizeof y);
            while (!xt.empty())xt.pop();
        }
        int t = isfill[j / 32] | z[j / 32] | y[j / 32];
        if (t & (1 << (j % 32)))
        {
            return 0;
        }
        t = 1 << (j % 32);
        isfill[j / 32] |= t;
        z[j / 32] |= t;
        y[j / 32] |= t;
        int tz = toz(z, 0, n);
        int ty = toy(y, 0, n);
        xt.push(j);
        for (int k = 0; k < n; k++)
        {
            sol(i + 1, k, n);
            if (i + 1 >= n)break;
        }
        toz(y, ty, n);
        toy(z, tz, n);
        isfill[j / 32] -= t;
        z[j / 32] -= t;
        y[j / 32] -= t;
        xt.pop();
        return 0;
    }
};
int main()
{
    Solution s;
    s.solveNQueens(8);

}